package interview.linkedlist;

import algorithm.model.ListNode;

/**
 * 判断列表是否有环
 * 有环，返回环的起点
 * 无环，返回null
 *
 * 要求：用O(1) 空间复杂度解决
 *
 * 思路：
 * (node2 x n*len) - (node1 x len) = m*Cycle 【node2比node1多走了环的整数个圈的长度】
 * 假设node步长为2.
 * 那么第一次相遇的时候，node2比node1走的长度多了1圈环.
 * 那么可以知道
 * 1环长度 = 起始到环开始 + 环上走了一点距离【cycle = y + m】
 * 那么从相遇点走到环的起点需要的长度 = 起始到环开始【cycle - m = y】
 * 那么把node1拉回head,然后node2,node1 一起以步长1走。
 * 当node1走了y的距离，node2也走了y的距离，这时候node1和node2就在环起始相遇了
 *
 *
 * 第一次相遇，说明有环。
 * 然后把node1拉回head，以步长为1一起往前推进，再一次相遇就是环的起点。
 *
 *
 * Created by yzy on 2021-02-02 14:40
 */
public class HashCycleII {

    public ListNode detectCycle(ListNode head) {
        ListNode node1 = head;
        ListNode node2 = head;

        boolean detected = false;
        while(node1!=null && node2!=null && node2.next!=null){
            node1 = node1.next;
            node2 = node2.next.next;
            if(node1==node2){
                detected = true;
                break;
            }
        }
        if(detected){
            node1 = head;
            while(node1 != node2){
                node1 = node1.next;
                node2 = node2.next;
            }
            return node1;
        }

        return null;
    }
}
